package Q31;

import java.text.NumberFormat;
import java.util.*;

public class test {
    public static void main(String[] args) {
        new Solution().nextPermutation(new int[]{2,3,4,5});
    }
}

/*
错误的解法

class Solution {
    public void nextPermutation(int[] nums) {
        List<List<Integer>> list = permuteUnique(nums);
        List<Integer> list1 = null;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            stringBuilder.append(nums[i]);
        }
        String s = stringBuilder.toString();
        int i1 = Integer.parseInt(s);
        List<Integer> ints = Arrays.asList(i1);
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i) == ints){
                list1 = list.get(i + 1);
            }
        }
        System.out.println(list1.size());
        int[] result = new int[list1.size()];
        for (int i = 0; i < list1.size(); i++) {
            result[i] = list1.get(i);
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length == 0) {
            return list;
        }
        //其实就是在这里先对数组进行一次排序，使得相同的元素相邻
        Arrays.sort(nums);
        int length = nums.length;
        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[length];
        dfs(nums,length,0,path,used,list);
        return list;
    }

    private void dfs(int[] nums, int length, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> list) {
        if(depth == length){
            list.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < length; i++) {
            //这里是最关键的一步，这里是在判断如果当前元素被使用过且当前元素和下一个元素相同而且下一个元素没有被使用过
            //说白了就是两个相同的且相邻的元素，一个被使用过，一个没有被使用过，如果是这种情况，就continue；
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            path.addLast(nums[i]);
            used[i] = true;
            dfs(nums,length,depth+1,path,used,list);
            path.removeLast();
            used[i] = false;
        }
    }
}
*/

class Solution {
    //两次遍历
    public static void nextPermutation(int[] nums) {
        //找到第一个满足a[i]<a[i+1]的，i右侧都是降序
        int i = nums.length - 2;
        while (i > 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        //从后往前找到第一个大于a[i]
        int j = nums.length - 1;
        while (j > 0 && nums[j] <= nums[i]) {
            j--;
        }
        if (j > 0) {
            swap(nums, i, j);
            //将i右侧变为升序
            for (int k = i + 1; k < nums.length - (k - i); k++) {
                swap(nums, k, nums.length - (k - i));
            }
        } else {
            for (int k = 0; k < nums.length - 1 - k; k++) {
                swap(nums, k, nums.length - 1 - k);
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int k = 0; k < nums.length; k++) {
            stringBuilder.append(nums[k]);
        }
        System.out.println(stringBuilder.toString());
    }

    public static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

